package com.zll.study.查找排序;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 描述
 * 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列
 *
 * 输入：
 * [[10,30],[20,60],[80,100],[150,180]]
 * 返回值：
 * [[10,60],[80,100],[150,180]]
 */
public class BM89合并区间 {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, (v1, v2) ->v1.start - v2.start);
        ArrayList<Interval> result = new ArrayList<Interval>();
        int index = -1;
        for(Interval interval :intervals){
            if(index == - 1 ||interval.start >result.get(index).end){
                // 区间 [a,b]  [c,d]   c 大于 b的话
                //不合并
                result.add(interval);
                index ++ ;
            }else{
                //如果 c 大于 b 那么就需要找一个最大的作为 右边的边界 因为数据start都从左到右排好序了
                result.get(index).end = Math.max(interval.end, result.get(index).end);
            }

        }
        return result;
    }
}

class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
}
